When did the Mahakala temple first come in existence, is difficult to tell. However, the event may be assigned to the Pre-historic period. Puranas narrate that it was first established by Prajapita Brahma. There is reference to the appointment of prince Kumarasena by king Chanda Pradyota in 6th c. BC for looking after the law and order situations of Mahakala temple. The punch-marked coins of Ujjain, belonging to 4th-3rd c. BC, bear the figure of Lord Siva on them. Mahakala temple is also mentioned in several ancient Indian poetic texts. According to these texts, the temple had been very magnificent and magnanimous. Its foundation and platform were built of stones. The temple rested on the wooden pillars. There had been no sikharas on the temples prior to the Gupta period. The roofs of temples had mostly been flat. Possibly due to this fact, Kalidasa in Raghuvansam described this temple as ‘Niketana’. The palace of the king had been in the vicinity of the temple. In the early part of the Meghadutam (Purva Megha), Kalidasa gives a fascinating description of the Mahakala temple. It appears that this Chandisvara temple might have been a unique example of the then art and architecture. It may be ascertained that how splendid had been the temple of the main Deity of that town which possessed multi-storeyed gold-plated palaces and buildings and the superb artistic grandeur. The temple was enclosed by high ramparts attached with the entry-gates. At twilight the lively rows of glittering lamps enlightened the temple-complex.
The whole atmosphere echoed with the sound of various musical instruments. Thecharming and well-decorated damsels added a lot in the aesthetic beauty of the temple. The echo of the Jaya-dhvani (Let the Lord be victories) of the assembly of the devotees was heard far and wide. Priests remained busy in worshipping the Deity and chanting eulogies. The Vedic hymns were recited and Stutis were sung, the painted walls and well-carved images projected the artistic heights of the day.
After the downfall of the Gupta empire, several dynasties including the Maitrakas, Chalukyas, Later Guptas, Kalachuris, Pusyabhutis, Gurjara Pratiharas, Rastrakutas etc. dominated the political scenerio in Ujjain one after the other. However, all bowed down before Mahakala and distributed endowments and alms to the deserving. During this period a number of temples of various gods and goddesses,Tirthas, Kundas, Vapis and gardens took shape in Avantika. Several Saivite temples including those of 84 Mahadevas existed here. This fact should specifically be underlined that when every nook and corner of Ujjain was dominated by religious monuments housed by the images of their respective deities, the development and progress of Mahakala temple and its religiocultural milieu was not at all neglected. Among many of the poetic texts composed during this period, which sung the significance and glamour of the temple, Harsacharit and Kadambari of Banabhatta, Naisadhacharit of Sri Harsa, and Navasahasamkacharit of Padmagupta are noteworthy. It so appears that during rhw Paramara period, a series of crisis prevailed over Ujjain and the Mahakala temple. In the Eighth decade of Eleventh c. AD, one Gazanavide commander invaded Malwa, looted it brutally and destroyed many temples and images. But very soon the Paramaras rejuvenated every thing. A contemporary Mahakala Inscription testifies the fact that during the later Eleventh c. and early twelfth c., the Mahakala temple was re-built during the reign of Udayaditya and Naravarman. It was built in the Bhumija style of architecture, very favourite to the Paramaras. Remains available in the temple-complex and the neighbouring places authenticate this fact. The temples of this style had been either Triratha or Pancharatha in plan. The main feature of identification of such temples had been its star-shaped plan and the sikhara. So far as the sikhara is concerned, urusrngas (mini-spires), generally of odd numbers, gradually decreasing in size in rows between the well-decorated spines (haravali or lata) rose up at the cardinal points from the Chityaas and the Sukanasas ultimately surmounted by the Amalaka. Every part of the temple was glutted with decorative motifs or images. Horizontally, the shrine from front to back was respectively divided in entrance, ardhamandapa, sanctum, antarala (vestibule) garbhagrha and Pradaksanapatha. Upper components of the temple rested on the strong and well-designed pillars and pilasters. Such temples, according to the contemporary Silpa-sastras contained the images of various god and goddesses, Nava Grahas (Nine planets), Apsaras (celestial damsels), female dancers, anucharas (attendants), Kichakas etc. The sculptural art of the temple had been very classical and multifarious. Besides the Saivite images of Nataraja, Kalyanasundara, Ravananugraha, Gajantaka, Sadasiva, Andhakasura-slayer, Lakulisa etc., the temples were adorned with the images of Ganesa, Paravati, Brahma, Visnu, Surya (Sun-god), Sapta Matrkas (Seven mother-goddesses) etc. These images had been very proportionate, well-decorated, sculpturally perfect and carved according to classical and Puranic texts. The worshipping and the conduct of rituals continued in some way or the other. Prabandha Chintamani, Vividha Tirtha Kalpataru, Prabandha Kosha all composed during 13th-14th c. reveal this fact. Similar mention is made in Vikramacharit and Bhojacharita composed in 15th c. AD. According to the epic Hammira Mahakavya, Hammira, the ruler of Ranathambor worshipped Lord Mahakala while his stay in Ujjain.
A few Sanads issued by the Sultans of Malwa and Mughal emperors have come to light in Ujjain which testifies that during the mediaeval period these Islamic rulers contributed some donations to priests for conducting worship, lighting the lamps and offering the prayers to Divinity for the safety of their reign. Thus it is evident that these Islamic rulers also had a respect for Mahakalesvara and they issued financial assistance for the appeasement of Hindu subjects too. Maratha regime was established in Ujjain in the fourth decade of Eighteenth c. The administration of Ujjain was assigned by Peshwa Bajirao-I to his faithful commander Ranoji Shinde, The diwan of Ranoji was Sukhatanakar Ramchandra Baba Shenavi who was very wealthy but unluckily issueless. On the suggestions of many learned Panditas and wel-wishers, he decided to invest his wealth for religious purposes. In this connection, he re-built the famous Mahakala temple in Ujjain during the 4th-5th decades of Eighteenth c. AD.